package toOffer;

/**
 * <h3>toOffer</h3>
 *
 * @author YuanAo
 * @date 2024/6/14 16:16
 * @description <p>山峰数组的顶部</p>
 */

import java.util.Arrays;

/**
 * 题目：
 * 题目：在一个长度大于或等于 3 的数组中，任意相邻的两个数字都不
 * 相等。该数组的前若干数字是递增的，之后的数字是递减的，因此它的值
 * 看起来像一座山峰。请找出山峰顶部，即数组中最大值的位置。例如，在
 * 数组[1, 3, 5, 4, 2]中，最大值是 5，输出它在数组中的下标 2。
 */
public class toOffer11_2_69 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 4, 2};
        System.out.println(peakIndexInMountainArray(arr));
    }

    /**
     * 思路：
     * 题目已经给好了说，前半部分是递增、后半部分是递减。在这个前提条件下，直接遍历数组，找到当前数比前一个数大、比后一个数小就行
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray1(int[] arr) {
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return  i;
        }
        return 0;
    }

    /**
     * 思路：二分法做判断
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray(int[] arr) {
        int mid = arr.length / 2;
        while (mid < arr.length - 1 && mid > 0){
            if (arr[mid] < arr[mid + 1] && arr[mid] > arr[mid - 1]){
                mid += 1;
            }else if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]){
                mid -= 1;
            }else if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){
                return mid;
            }
        }
        return 0;
    }

}
